//One way to serialize a binary tree is to use pre-order traversal. When we enco
//unter a non-null node, we record the node's value. If it is a null node, we reco
//rd using a sentinel value such as #. 
//
// 
//     _9_
//    /   \
//   3     2
//  / \   / \
// 4   1  #  6
/// \ / \   / \
//# # # #   # #
// 
//
// For example, the above binary tree can be serialized to the string "9,3,4,#,#
//,1,#,#,2,#,6,#,#", where # represents a null node. 
//
// Given a string of comma separated values, verify whether it is a correct preo
//rder traversal serialization of a binary tree. Find an algorithm without reconst
//ructing the tree. 
//
// Each comma separated value in the string must be either an integer or a chara
//cter '#' representing null pointer. 
//
// You may assume that the input format is always valid, for example it could ne
//ver contain two consecutive commas such as "1,,3". 
//
// Example 1: 
//
// 
//Input: "9,3,4,#,#,1,#,#,2,#,6,#,#"
//Output: true 
//
// Example 2: 
//
// 
//Input: "1,#"
//Output: false
// 
//
// Example 3: 
//
// 
//Input: "9,#,#,1"
//Output: false Related Topics 栈


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    fun isValidSerialization(preorder: String): Boolean {
        var count = 1
        for(s in preorder.split(",")){
            count--
            if(count < 0){
                return false
            }
            if(!"#".equals(s)){
                count+=2
            }
        }
        return count == 0
    }
}
//leetcode submit region end(Prohibit modification and deletion)
